#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

#define MAX_REQUESTS 100

// 函数声明
void fifo(int requests[], int n, int head);                  // 先来先服务
void sstf(int requests[], int n, int head);                  // 最短寻道
void scan(int requests[], int n, int head, int disk_size);   // 电梯算法
void c_scan(int requests[], int n, int head, int disk_size); // 循环扫描
void sort(int arr[], int n);

int main()
{
    int requests[MAX_REQUESTS];
    int n, head, disk_size;
    int choice;

    int t_requests[] = {55, 58, 39, 18, 90, 160, 150, 38, 184};

    printf("请输入磁盘请求数量: \n");

    n = 9;
    // scanf("%d", &n);

    printf("请输入磁盘请求序列: \n");
    for (int i = 0; i < n; i++)
    {
        requests[i] = t_requests[i];
        // scanf("%d", &requests[i]);
    }

    printf("请输入当前磁头位置: \n");
    head = 100;
    // scanf("%d", &head);

    // printf("请输入磁盘大小(最大磁道号): ");
    // scanf("%d", &disk_size);

    while (1)
    {
        printf("\n磁盘调度算法菜单:\n");
        printf("1. FIFO (先来先服务)\n");
        printf("2. SSTF (最短寻道时间优先)\n");
        printf("3. SCAN (电梯算法)\n");
        printf("4. C-SCAN (循环扫描)\n");
        printf("5. 退出\n");
        printf("请选择算法: ");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            fifo(requests, n, head);
            break;
        case 2:
            sstf(requests, n, head);
            break;
        case 3:
            scan(requests, n, head, disk_size);
            break;
        case 4:
            c_scan(requests, n, head, disk_size);
            break;
        case 5:
            exit(0);
        default:
            printf("无效选择!\n");
        }
    }

    return 0;
}

// FIFO算法实现
void fifo(int requests[], int n, int head)
{
    int total_movement = 0;
    printf("\nFIFO调度顺序:\n");
    printf("%d -> ", head);

    for (int i = 0; i < n; i++)
    {
        total_movement += abs(head - requests[i]);
        head = requests[i];
        if (i == n - 1)
            printf("%d\n", head);
        else
            printf("%d -> ", head);
    }

    printf("总磁头移动距离: %d\n", total_movement);
}

// SSTF算法实现
void sstf(int requests[], int n, int head)
{
    int total_movement = 0;
    int visited[MAX_REQUESTS] = {0};

    printf("\nSSTF调度顺序:\n");
    printf("%d -> ", head);

    for (int i = 0; i < n; i++)
    {
        int min_distance = INT_MAX;
        int min_index = -1;

        for (int j = 0; j < n; j++)
        {
            if (!visited[j])
            {
                int distance = abs(head - requests[j]);
                if (distance < min_distance)
                {
                    min_distance = distance;
                    min_index = j;
                }
            }
        }

        visited[min_index] = 1;
        total_movement += min_distance;
        head = requests[min_index];

        if (i == n - 1)
            printf("%d\n", head);
        else
            printf("%d -> ", head);
    }

    printf("总磁头移动距离: %d\n", total_movement);
}

// SCAN算法实现
void scan(int requests[], int n, int head, int disk_size)
{
    int total_movement = 0;
    int sorted_requests[MAX_REQUESTS];

    // 复制请求数组并排序
    for (int i = 0; i < n; i++)
    {
        sorted_requests[i] = requests[i];
    }
    sort(sorted_requests, n);

    printf("\nSCAN调度顺序:\n");
    printf("%d -> ", head);

    // 找到第一个大于等于head的请求
    int index = 0;
    while (index < n && sorted_requests[index] < head)
    {
        index++;
    }

    // 向磁盘末端移动
    for (int i = index; i < n; i++)
    {
        total_movement += abs(head - sorted_requests[i]);
        head = sorted_requests[i];
        printf("%d -> ", head);
    }
    // 反向移动
    for (int i = index - 1; i >= 0; i--)
    {
        total_movement += abs(head - sorted_requests[i]);
        head = sorted_requests[i];
        if (i == 0)
            printf("%d\n", head);
        else
            printf("%d -> ", head);
    }

    printf("总磁头移动距离: %d\n", total_movement);
}

// C-SCAN算法实现
void c_scan(int requests[], int n, int head, int disk_size)
{
    int total_movement = 0;
    int sorted_requests[MAX_REQUESTS];

    // 复制请求数组并排序
    for (int i = 0; i < n; i++)
    {
        sorted_requests[i] = requests[i];
    }
    sort(sorted_requests, n);

    printf("\nC-SCAN调度顺序:\n");
    printf("%d -> ", head);

    // 找到第一个大于等于head的请求
    int index = 0;
    while (index < n && sorted_requests[index] < head)
    {
        index++;
    }

    // 向磁盘末端移动
    for (int i = index; i < n; i++)
    {
        total_movement += abs(head - sorted_requests[i]);
        head = sorted_requests[i];
        printf("%d -> ", head);
    }
    // 跳转到磁盘开始
    total_movement += head - sorted_requests[0]; // 从末尾到开始的距离
    head = sorted_requests[0];
    printf("%d -> ", head);

    // 从磁盘开始继续移动
    for (int i = 1; i < index; i++)
    {
        total_movement += abs(head - sorted_requests[i]);
        head = sorted_requests[i];
        if (i == index - 1)
            printf("%d\n", head);
        else
            printf("%d -> ", head);
    }

    printf("总磁头移动距离: %d\n", total_movement);
}

// 辅助函数：冒泡排序
void sort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}